package visualizer.client.algorithms.rBst;

import com.google.gwt.user.client.Random;
import visualizer.client.algorithms.AlgoResult;
import visualizer.client.algorithms.Algorithm;
import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;

import java.util.ArrayList;
import java.util.List;

import static visualizer.client.utils.VisualizerUtils.DEFAULT_OUTER_COLOR;

/**
 * User: DDovzhenko
 * Date: 07.01.14
 * Time: 18:26
 */
public class RBSTRemovingAlgorithm implements Algorithm {
    private BinaryTree tree;
    private List<AlgoResult> results = new ArrayList<AlgoResult>();
    boolean isRemoved;

    @Override
    public AlgoResult performAlgorithmToStep(BinaryTree tree, int step, int inputValue) {
        return results.get(step);
    }

    @Override
    public int getStepsCount(BinaryTree binaryTree, int inputValue) {
        results.clear();
        isRemoved = false;
        results.add(new AlgoResult(binaryTree.copyTree(false), "Удаление узла с ключом " + inputValue + ". Сперва найдем этот узел, далее объединим левое и правое поддеревья найденного узла, удалим узел и возвратим корень объединенного дерева."));
        tree = binaryTree.copyTree(false);
        tree.refreshSizes();
        tree.setRootNode(remove(tree.getRoot(), inputValue));
        results.add(new AlgoResult(tree, "Узел с ключом " + inputValue + (isRemoved ? " успешно удален" : " не существует и не может быть удален")));
        return results.size();
    }

    public BNode remove(BNode root, int x) {
        if (root == null) {
            return null;
        }
        root.setOuterColor("red");
        if (root.getValue() == x) {
            isRemoved = true;
            root.setInnerColor("lightblue");
            results.add(new AlgoResult(tree.copyTree(true), "Узел найден, объединим его левое и правое поддеревья. Выбор корня будет осуществляться случайным образом. " +
                    "Если размер левого дерева равен n, правого — m, " +
                    "тогда левый узел выбирается новым корнем с вероятностью n/(n+m), а правый — с вероятностью m/(n+m)"));
            return merge(root.getLeftBNode(), root.getRightBNode());
        } else {
            if (x < root.getValue()) {
                results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: ключ " + x + " меньше ключа " + root.getValue() + ", обрабатываем левое поддерево"));
                setDefaultColorIfNotNull(root, root.getLeftBNode());
                root.setLeftBNode(remove(root.getLeftBNode(), x));
            } else {
                results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: ключ " + x + " больше ключа " + root.getValue() + ", обрабатываем правое поддерево"));
                setDefaultColorIfNotNull(root, root.getRightBNode());
                root.setRightBNode(remove(root.getRightBNode(), x));
            }
            tree.updateSize(root);
            return root;
        }
    }

    public BNode merge(BNode p, BNode q) {
        if (p == null) {
            return q;
        }

        if (q == null) {
            return p;
        }
        p.setOuterColor("red");
        q.setOuterColor("red");
        double probability = ((int)((double)p.getSize() / (p.getSize() + q.getSize()) * 10000)) / 100.0;
        results.add(new AlgoResult(tree.copyTree(true), "Рассмотрим узлы с ключами " + p.getValue() + " и " + q.getValue() + ". Выберем из них узел, который будет корнем в объединенном дереве. " +
                "Узел с ключом " + p.getValue() + " будет корнем с вероятностью " + probability + "%. " +
                "Узел с ключом " + q.getValue() + " будет корнем с вероятностью " + (100 - probability) + "%."));
        if (Random.nextInt(p.getSize() + q.getSize()) < p.getSize()) {
            q.setOuterColor(DEFAULT_OUTER_COLOR);
            p.setOuterColor("green");
            results.add(new AlgoResult(tree.copyTree(true), "Новым корнем является узел с ключом " + p.getValue()));
            p.setRightBNode(merge(p.getRightBNode(), q));
            tree.updateSize(p);
            return p;
        } else {
            p.setOuterColor(DEFAULT_OUTER_COLOR);
            q.setOuterColor("green");
            results.add(new AlgoResult(tree.copyTree(true), "Новым корнем является узел с ключом " + q.getValue()));
            q.setLeftBNode(merge(p, q.getLeftBNode()));
            tree.updateSize(q);
            return q;
        }
    }

    private void setDefaultColorIfNotNull(BNode node, BNode checkNode) {
        if (checkNode != null) {
            node.setOuterColor(DEFAULT_OUTER_COLOR);
        }
    }
}
